class Solution {
    struct myCmp
    {
        bool operator()(const pair<int, int> &p1, const pair<int, int> &p2)
        {
            return p1.first + p1.second <  p2.first + p2.second;
        }
    };
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        // 使用小根堆存储三元组
        int n = nums1.size(), m = nums2.size();
        vector<vector<int>> ret;
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> heap;

        // 至多k个入堆     
        for(int i = 0; i < min(n, k); i++)
            heap.emplace(nums1[i] + nums2[0], i, 0);

        while(ret.size() < k)
        {
            auto [_, i, j] = heap.top();
            heap.pop();
            ret.push_back({ nums1[i], nums2[j] });
            if(j + 1 < m)
                heap.emplace(nums1[i] + nums2[j + 1], i, j + 1);
        }
        return ret;






        // 下面这种解法时间复杂度太高了，过不去
        // // 和最小的 k 对数 - 大堆
        // priority_queue<pair<int, int>, vector<pair<int, int>>, myCmp> heap;
        // for(int &x1 : nums1)
        // {
        //     for(int &x2 : nums2)
        //     {
        //         heap.push(make_pair(x1, x2));
        //         if(heap.size() > k)
        //             heap.pop();
        //     }
        // }

        // vector<vector<int>> ret;
        // while(heap.size())
        // {
        //     pair<int, int> p = heap.top();
        //     ret.push_back({ p.first, p.second });
        //     heap.pop();
        // }
        // return ret;
    }
};